#ifndef JALGORITHMS_H
#define JALGORITHMS_H

#include "../jthreadpool_global.h"

/*
    Warning: The contents of JAlgorithmsPrivate is not a part of the public API
    and may be changed from version to version or even be completely removed.
*/
namespace JAlgorithmsPrivate {

template <typename RandomAccessIterator, typename T, typename LessThan>
J_OUTOFLINE_TEMPLATE void jSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan);
template <typename RandomAccessIterator, typename T>
inline void jSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy);

template <typename RandomAccessIterator, typename T, typename LessThan>
J_OUTOFLINE_TEMPLATE void jStableSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan);
template <typename RandomAccessIterator, typename T>
inline void jStableSortHelper(RandomAccessIterator, RandomAccessIterator, const T &);

template <typename RandomAccessIterator, typename T, typename LessThan>
J_OUTOFLINE_TEMPLATE RandomAccessIterator jLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
template <typename RandomAccessIterator, typename T, typename LessThan>
J_OUTOFLINE_TEMPLATE RandomAccessIterator jUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);
template <typename RandomAccessIterator, typename T, typename LessThan>
J_OUTOFLINE_TEMPLATE RandomAccessIterator jBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan);

}

template <typename InputIterator, typename OutputIterator>
inline OutputIterator jCopy(InputIterator begin, InputIterator end, OutputIterator dest)
{
    while (begin != end)
        *dest++ = *begin++;
    return dest;
}

template <typename BiIterator1, typename BiIterator2>
inline BiIterator2 jCopyBackward(BiIterator1 begin, BiIterator1 end, BiIterator2 dest)
{
    while (begin != end)
        *--dest = *--end;
    return dest;
}

template <typename InputIterator1, typename InputIterator2>
inline bool jEqual(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
{
    for (; first1 != last1; ++first1, ++first2)
        if (!(*first1 == *first2))
            return false;
    return true;
}

template <typename ForwardIterator, typename T>
inline void jFill(ForwardIterator first, ForwardIterator last, const T &val)
{
    for (; first != last; ++first)
        *first = val;
}

template <typename Container, typename T>
inline void jFill(Container &container, const T &val)
{
    jFill(container.begin(), container.end(), val);
}

template <typename InputIterator, typename T>
inline InputIterator jFind(InputIterator first, InputIterator last, const T &val)
{
    while (first != last && !(*first == val))
        ++first;
    return first;
}

template <typename Container, typename T>
inline typename Container::const_iterator jFind(const Container &container, const T &val)
{
    return jFind(container.constBegin(), container.constEnd(), val);
}

template <typename InputIterator, typename T, typename Size>
inline void jCount(InputIterator first, InputIterator last, const T &value, Size &n)
{
    for (; first != last; ++first)
        if (*first == value)
            ++n;
}

template <typename Container, typename T, typename Size>
inline void jCount(const Container &container, const T &value, Size &n)
{
    jCount(container.constBegin(), container.constEnd(), value, n);
}

template <typename T>
class jLess
{
public:
    inline bool operator()(const T &t1, const T &t2) const
    {
        return (t1 < t2);
    }
};

template <typename T>
class jGreater
{
public:
    inline bool operator()(const T &t1, const T &t2) const
    {
        return (t2 < t1);
    }
};

template <typename RandomAccessIterator>
inline void jSort(RandomAccessIterator start, RandomAccessIterator end)
{
    if (start != end)
        JAlgorithmsPrivate::jSortHelper(start, end, *start);
}

template <typename RandomAccessIterator, typename LessThan>
inline void jSort(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)
{
    if (start != end)
        JAlgorithmsPrivate::jSortHelper(start, end, *start, lessThan);
}

template<typename Container>
inline void jSort(Container &c)
{
    if (!c.empty())
        JAlgorithmsPrivate::jSortHelper(c.begin(), c.end(), *c.begin());
}

template <typename RandomAccessIterator>
inline void jStableSort(RandomAccessIterator start, RandomAccessIterator end)
{
    if (start != end)
        JAlgorithmsPrivate::jStableSortHelper(start, end, *start);
}

template <typename RandomAccessIterator, typename LessThan>
inline void jStableSort(RandomAccessIterator start, RandomAccessIterator end, LessThan lessThan)
{
    if (start != end)
        JAlgorithmsPrivate::jStableSortHelper(start, end, *start, lessThan);
}

template<typename Container>
inline void jStableSort(Container &c)
{
    if (!c.empty())
        JAlgorithmsPrivate::jStableSortHelper(c.begin(), c.end(), *c.begin());
}

template <typename RandomAccessIterator, typename T>
J_OUTOFLINE_TEMPLATE RandomAccessIterator jLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
{
    // Implementation is duplicated from JAlgorithmsPrivate to keep existing code
    // compiling. We have to allow using *begin and value with different types,
    // and then implementing operator< for those types.
    RandomAccessIterator middle;
    int n = end - begin;
    int half;

    while (n > 0) {
        half = n >> 1;
        middle = begin + half;
        if (*middle < value) {
            begin = middle + 1;
            n -= half + 1;
        } else {
            n = half;
        }
    }
    return begin;
}

template <typename RandomAccessIterator, typename T, typename LessThan>
J_OUTOFLINE_TEMPLATE RandomAccessIterator jLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
{
    return JAlgorithmsPrivate::jLowerBoundHelper(begin, end, value, lessThan);
}

template <typename Container, typename T>
J_OUTOFLINE_TEMPLATE typename Container::const_iterator jLowerBound(const Container &container, const T &value)
{
    return JAlgorithmsPrivate::jLowerBoundHelper(container.constBegin(), container.constEnd(), value, qLess<T>());
}

template <typename RandomAccessIterator, typename T>
J_OUTOFLINE_TEMPLATE RandomAccessIterator jUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
{
    // Implementation is duplicated from JAlgorithmsPrivate.
    RandomAccessIterator middle;
    int n = end - begin;
    int half;

    while (n > 0) {
        half = n >> 1;
        middle = begin + half;
        if (value < *middle) {
            n = half;
        } else {
            begin = middle + 1;
            n -= half + 1;
        }
    }
    return begin;
}

template <typename RandomAccessIterator, typename T, typename LessThan>
J_OUTOFLINE_TEMPLATE RandomAccessIterator jUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
{
    return JAlgorithmsPrivate::jUpperBoundHelper(begin, end, value, lessThan);
}

template <typename Container, typename T>
J_OUTOFLINE_TEMPLATE typename Container::const_iterator jUpperBound(const Container &container, const T &value)
{
    return JAlgorithmsPrivate::jUpperBoundHelper(container.constBegin(), container.constEnd(), value, qLess<T>());
}

template <typename RandomAccessIterator, typename T>
J_OUTOFLINE_TEMPLATE RandomAccessIterator jBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
{
    // Implementation is duplicated from QAlgorithmsPrivate.
    RandomAccessIterator it = jLowerBound(begin, end, value);

    if (it == end || value < *it)
        return end;

    return it;
}

template <typename RandomAccessIterator, typename T, typename LessThan>
J_OUTOFLINE_TEMPLATE RandomAccessIterator jBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
{
    return JAlgorithmsPrivate::jBinaryFindHelper(begin, end, value, lessThan);
}

template <typename Container, typename T>
J_OUTOFLINE_TEMPLATE typename Container::const_iterator jBinaryFind(const Container &container, const T &value)
{
    return JAlgorithmsPrivate::jBinaryFindHelper(container.constBegin(), container.constEnd(), value, qLess<T>());
}

template <typename ForwardIterator>
J_OUTOFLINE_TEMPLATE void jDeleteAll(ForwardIterator begin, ForwardIterator end)
{
    while (begin != end) {
        delete *begin;
        ++begin;
    }
}

template <typename Container>
inline void jDeleteAll(const Container &c)
{
    jDeleteAll(c.begin(), c.end());
}

/*
    Warning: The contents of JAlgorithmsPrivate is not a part of the public API
    and may be changed from version to version or even be completely removed.
*/
namespace JAlgorithmsPrivate {

template <typename RandomAccessIterator, typename T, typename LessThan>
J_OUTOFLINE_TEMPLATE void jSortHelper(RandomAccessIterator start, RandomAccessIterator end, const T &t, LessThan lessThan)
{
top:
    int span = int(end - start);
    if (span < 2)
        return;

    --end;
    RandomAccessIterator low = start, high = end - 1;
    RandomAccessIterator pivot = start + span / 2;

    if (lessThan(*end, *start))
        jSwap(*end, *start);
    if (span == 2)
        return;

    if (lessThan(*pivot, *start))
        jSwap(*pivot, *start);
    if (lessThan(*end, *pivot))
        jSwap(*end, *pivot);
    if (span == 3)
        return;

    jSwap(*pivot, *end);

    while (low < high) {
        while (low < high && lessThan(*low, *end))
            ++low;

        while (high > low && lessThan(*end, *high))
            --high;

        if (low < high) {
            jSwap(*low, *high);
            ++low;
            --high;
        } else {
            break;
        }
    }

    if (lessThan(*low, *end))
        ++low;

    jSwap(*end, *low);
    jSortHelper(start, low, t, lessThan);

    start = low + 1;
    ++end;
    goto top;
}

template <typename RandomAccessIterator, typename T>
inline void jSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
{
    jSortHelper(begin, end, dummy, jLess<T>());
}

template <typename RandomAccessIterator>
J_OUTOFLINE_TEMPLATE void jReverse(RandomAccessIterator begin, RandomAccessIterator end)
{
    --end;
    while (begin < end)
        jSwap(*begin++, *end--);
}

template <typename RandomAccessIterator>
J_OUTOFLINE_TEMPLATE void jRotate(RandomAccessIterator begin, RandomAccessIterator middle, RandomAccessIterator end)
{
    jReverse(begin, middle);
    jReverse(middle, end);
    jReverse(begin, end);
}

template <typename RandomAccessIterator, typename T, typename LessThan>
J_OUTOFLINE_TEMPLATE void jMerge(RandomAccessIterator begin, RandomAccessIterator pivot, RandomAccessIterator end, T &t, LessThan lessThan)
{
    const int len1 = pivot - begin;
    const int len2 = end - pivot;

    if (len1 == 0 || len2 == 0)
        return;

    if (len1 + len2 == 2) {
        if (lessThan(*(begin + 1), *(begin)))
            jSwap(*begin, *(begin + 1));
        return;
    }

    RandomAccessIterator firstCut;
    RandomAccessIterator secondCut;
    int len2Half;
    if (len1 > len2) {
        const int len1Half = len1 / 2;
        firstCut = begin + len1Half;
        secondCut = qLowerBound(pivot, end, *firstCut, lessThan);
        len2Half = secondCut - pivot;
    } else {
        len2Half = len2 / 2;
        secondCut = pivot + len2Half;
        firstCut = qUpperBound(begin, pivot, *secondCut, lessThan);
    }

    jRotate(firstCut, pivot, secondCut);
    const RandomAccessIterator newPivot = firstCut + len2Half;
    jMerge(begin, firstCut, newPivot, t, lessThan);
    jMerge(newPivot, secondCut, end, t, lessThan);
}

template <typename RandomAccessIterator, typename T, typename LessThan>
J_OUTOFLINE_TEMPLATE void jStableSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &t, LessThan lessThan)
{
    const int span = end - begin;
    if (span < 2)
       return;

    const RandomAccessIterator middle = begin + span / 2;
    jStableSortHelper(begin, middle, t, lessThan);
    jStableSortHelper(middle, end, t, lessThan);
    jMerge(begin, middle, end, t, lessThan);
}

template <typename RandomAccessIterator, typename T>
inline void jStableSortHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &dummy)
{
    jStableSortHelper(begin, end, dummy, jLess<T>());
}

template <typename RandomAccessIterator, typename T, typename LessThan>
J_OUTOFLINE_TEMPLATE RandomAccessIterator jLowerBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
{
    RandomAccessIterator middle;
    int n = int(end - begin);
    int half;

    while (n > 0) {
        half = n >> 1;
        middle = begin + half;
        if (lessThan(*middle, value)) {
            begin = middle + 1;
            n -= half + 1;
        } else {
            n = half;
        }
    }
    return begin;
}


template <typename RandomAccessIterator, typename T, typename LessThan>
J_OUTOFLINE_TEMPLATE RandomAccessIterator jUpperBoundHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
{
    RandomAccessIterator middle;
    int n = end - begin;
    int half;

    while (n > 0) {
        half = n >> 1;
        middle = begin + half;
        if (lessThan(value, *middle)) {
            n = half;
        } else {
            begin = middle + 1;
            n -= half + 1;
        }
    }
    return begin;
}

template <typename RandomAccessIterator, typename T, typename LessThan>
J_OUTOFLINE_TEMPLATE RandomAccessIterator jBinaryFindHelper(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
{
    RandomAccessIterator it = jLowerBoundHelper(begin, end, value, lessThan);

    if (it == end || lessThan(value, *it))
        return end;

    return it;
}

} //namespace JAlgorithmsPrivate

#endif // JALGORITHMS_H
